// https://leetcode.cn/problems/reverse-pairs/description/

// 算法思路总结：
// 1. 归并排序过程中统计重要逆序对数量
// 2. 重要逆序对定义：i < j 且 nums[i] > 2*nums[j]
// 3. 在合并前先统计满足条件的逆序对
// 4. 使用双指针避免暴力枚举提高效率
// 5. 时间复杂度：O(n log n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int reversePairs(vector<int>& nums) 
    {
        int m = nums.size();

        int ret = 0;
        mergesort(nums, 0, m - 1, ret);

        return ret;
    }

    void mergesort(vector<int>& nums, int left, int right, int& ret)
    {
        if (left >= right)
        {
            return ;
        }

        int mid = (left + right) >> 1;
        mergesort(nums, left, mid, ret);
        mergesort(nums, mid + 1, right, ret);

        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
        {
            if ((long long)nums[cur1] > 2 * (long long)nums[cur2])
            {
                ret += right - cur2 + 1;
                cur1++;
            }
            else
            {
                cur2++;
            }
        }

        cur1 = left, cur2 = mid + 1;
        int index = 0;
        vector<int> tmp(right - left + 1);

        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmp[index++] = nums[cur2++];
            }
            else
            {
                tmp[index++] = nums[cur1++];
            }
        }

        while (cur1 <= mid)
        {
            tmp[index++] = nums[cur1++];
        }

        while (cur2 <= right)
        {
            tmp[index++] = nums[cur2++];
        } 

        for (int i = left ; i <= right ; i++)
        {
            nums[i] = tmp[i - left];
        }
    }
};


int main()
{
    vector<int> nums1 = {1,3,2,3,1}, nums2 = {2,4,3,5,1};
    Solution sol;

    cout << sol.reversePairs(nums1) << endl;
    cout << sol.reversePairs(nums2) << endl;

    return 0;
}